home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 15 / CU Amiga Magazine's Super CD-ROM 15 (1997)(EMAP Images)(GB)[!][issue 1997-10].iso / CUCD / Graphics / Ghostscript / source / idict.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-04  |  30.7 KB  |  1,004 lines
  1. /* Copyright (C) 1989, 1996, 1997 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* idict.c */
  20. /* Dictionaries for Ghostscript */
  21. #include "string_.h"            /* for strlen */
  22. #include "ghost.h"
  23. #include "errors.h"
  24. #include "ialloc.h"
  25. #include "idebug.h"            /* for debug_print_name */
  26. #include "inamedef.h"
  27. #include "ipacked.h"
  28. #include "isave.h"            /* for value cache in names */
  29. #include "store.h"
  30. #include "idict.h"            /* interface definition */
  31. #include "dstack.h"            /* interface & some implementation */
  32. #include "iutil.h"
  33. #include "ivmspace.h"            /* for store check */
  34.  
  35. /*
  36.  * A dictionary of capacity M is a structure of four elements (refs):
  37.  *
  38.  *    keys - a t_shortarray or t_array of M+1 elements, containing
  39.  *    the keys.
  40.  *
  41.  *    values - a t_array of M+1 elements, containing the values.
  42.  *
  43.  *    count - a t_integer whose value tells how many entries are
  44.  *    occupied (N).
  45.  *
  46.  *    maxlength - a t_integer whose value gives the client's view of
  47.  *    the capacity (C).  C may be less than M (see below).
  48.  *
  49.  * C < M is possible because on large-memory systems, we usually round up M
  50.  * so that M is a power of 2 (see idict.h for details); this allows us to
  51.  * use masking rather than division for computing the initial hash probe.
  52.  * However, C is always the maxlength specified by the client, so clients
  53.  * get a consistent story.
  54.  *
  55.  * As noted above, the keys may be either in packed or unpacked form.
  56.  * The markers for unused and deleted entries are different in the two forms.
  57.  * In the packed form:
  58.  *    unused entries contain packed_key_empty;
  59.  *    deleted entries contain packed_key_deleted.
  60.  * In the unpacked form:
  61.  *    unused entries contain a literal null;
  62.  *    deleted entries contain an executable null.
  63.  *
  64.  * The first entry is always marked deleted, to reduce the cost of the
  65.  * wrap-around check.
  66.  *
  67.  * Note that if the keys slot in the dictionary is new,
  68.  * all the key slots are new (more recent than the last save).
  69.  * We use this fact to avoid saving stores into packed keys
  70.  * for newly created dictionaries.
  71.  *
  72.  * Note that name keys with indices above packed_name_max_index require using
  73.  * the unpacked form.  */
  74. #define dict_is_packed(dct) r_has_type(&(dct)->keys, t_shortarray)
  75. #define packed_key_empty (pt_tag(pt_integer) + 0)
  76. #define packed_key_deleted (pt_tag(pt_integer) + 1)
  77. #define packed_key_impossible pt_tag(pt_full_ref)    /* never matches */
  78. #define packed_name_key(nidx)\
  79.   ((nidx) <= packed_name_max_index ? pt_tag(pt_literal_name) + (nidx) :\
  80.    packed_key_impossible)
  81. /*
  82.  * Using a special mark for deleted entries causes lookup time to degrade
  83.  * as entries are inserted and deleted.  This is not a problem, because
  84.  * entries are almost never deleted.
  85.  */
  86. #define d_maxlength(dct) ((uint)((dct)->maxlength.value.intval))
  87. #define d_set_maxlength(dct,siz) ((dct)->maxlength.value.intval = (siz))
  88. #define nslots(dct) r_size(&(dct)->values)
  89. #define npairs(dct) (nslots(dct) - 1)
  90. #define d_length(dct) ((uint)((dct)->count.value.intval))
  91.  
  92. /*
  93.  * Define the size of the largest valid dictionary.
  94.  * This is limited by the size field of the keys and values refs,
  95.  * and by the enumeration interface, which requires the size to
  96.  * fit in an int.  As it happens, max_array_size will always be
  97.  * smaller than max_int.
  98.  */
  99. const uint dict_max_size = max_array_size - 1;
  100.  
  101. /* Define whether dictionaries expand automatically when full. */
  102. bool dict_auto_expand = false;
  103.  
  104. /* Define whether dictionaries are packed by default. */
  105. bool dict_default_pack = true;
  106.  
  107. /* Cached values from the top element of the dictionary stack. */
  108. /* See dstack.h for details. */
  109. int dsspace;                /* see dstack.h */
  110. const ref_packed *dtop_keys;
  111. uint dtop_npairs;
  112. ref *dtop_values;
  113.  
  114. /* Forward references */
  115. private int dict_create_contents(P3(uint size, const ref *pdref, bool pack));
  116.  
  117. /* Debugging statistics */
  118. #ifdef DEBUG
  119. long dn_lookups;        /* total lookups */
  120. long dn_1probe;            /* successful lookups on only 1 probe */
  121. long dn_2probe;            /* successful lookups on 2 probes */
  122. /* Wrappers for dict_find and dict_find_name_by_index */
  123. int real_dict_find(P3(const ref *pdref, const ref *key, ref **ppvalue));
  124. int
  125. dict_find(const ref *pdref, const ref *pkey, ref **ppvalue)
  126. {    dict *pdict = pdref->value.pdict;
  127.     int code = real_dict_find(pdref, pkey, ppvalue);
  128.  
  129.     dn_lookups++;
  130.     if ( r_has_type(pkey, t_name) && dict_is_packed(pdict) )
  131.     {    uint nidx = name_index(pkey);
  132.         uint hash =
  133.           dict_hash_mod(dict_name_index_hash(nidx), npairs(pdict)) + 1;
  134.         if (  pdict->keys.value.packed[hash] ==
  135.                 pt_tag(pt_literal_name) + nidx
  136.            )
  137.           dn_1probe++;
  138.         else if (  pdict->keys.value.packed[hash - 1] ==
  139.                  pt_tag(pt_literal_name) + nidx
  140.             )
  141.           dn_2probe++;
  142.     }
  143.     /* Do the cheap flag test before the expensive remainder test. */
  144.     if ( gs_debug_c('d') && !(dn_lookups % 1000) )
  145.       dprintf3("[d]lookups=%ld 1probe=%ld 2probe=%ld\n",
  146.            dn_lookups, dn_1probe, dn_2probe);
  147.     return code;
  148. }
  149. #define dict_find real_dict_find
  150. ref *real_dict_find_name_by_index(P1(uint nidx));
  151. ref *
  152. dict_find_name_by_index(uint nidx)
  153. {    ref *pvalue = real_dict_find_name_by_index(nidx);
  154.     dict *pdict = dsp->value.pdict;
  155.  
  156.     dn_lookups++;
  157.     if ( dict_is_packed(pdict) )
  158.     {    uint hash =
  159.           dict_hash_mod(dict_name_index_hash(nidx), npairs(pdict)) + 1;
  160.         if (  pdict->keys.value.packed[hash] ==
  161.                 pt_tag(pt_literal_name) + nidx
  162.            )
  163.           dn_1probe++;
  164.         else if (  pdict->keys.value.packed[hash - 1] ==
  165.                  pt_tag(pt_literal_name) + nidx
  166.             )
  167.           dn_2probe++;
  168.     }
  169.     /* Do the cheap flag test before the expensive remainder test. */
  170.     if ( gs_debug_c('d') && !(dn_lookups % 1000) )
  171.       dprintf3("[d]lookups=%ld 1probe=%ld 2probe=%ld\n",
  172.            dn_lookups, dn_1probe, dn_2probe);
  173.     return pvalue;
  174. }
  175. #define dict_find_name_by_index real_dict_find_name_by_index
  176. #endif
  177.  
  178. /* Round up the size of a dictionary.  Return 0 if too large. */
  179. uint
  180. dict_round_size_small(uint rsize)
  181. {    return (rsize > dict_max_size ? 0 : rsize);
  182. }
  183. uint
  184. dict_round_size_large(uint rsize)
  185. {    /* Round up to a power of 2 if not huge. */
  186.     /* If the addition overflows, the new rsize will be zero, */
  187.     /* which will (correctly) be interpreted as a limitcheck. */
  188.     if ( rsize > dict_max_non_huge )
  189.       return (rsize > dict_max_size ? 0 : rsize);
  190.     while ( rsize & (rsize - 1) )
  191.       rsize = (rsize | (rsize - 1)) + 1;
  192.     return (rsize <= dict_max_size ? rsize : dict_max_non_huge);
  193. }
  194.  
  195. /* Create a dictionary in the current VM space. */
  196. int
  197. dict_create(uint size, ref *pdref)
  198. {    ref arr;
  199.     int code = ialloc_ref_array(&arr, a_all, sizeof(dict) / sizeof(ref),
  200.                     "dict_create");
  201.     ref dref;
  202.  
  203.     if ( code < 0 )
  204.       return code;
  205.     make_tav_new(&dref, t_dictionary, r_space(&arr) | a_all,
  206.              pdict, (dict *)arr.value.refs);
  207.     code = dict_create_contents(size, &dref, dict_default_pack);
  208.     if ( code < 0 )
  209.       return code;
  210.     *pdref = dref;
  211.     return 0;
  212. }
  213. /* Create unpacked keys for a dictionary. */
  214. /* The keys are allocated in the same VM space as the dictionary. */
  215. private int
  216. dict_create_unpacked_keys(uint asize, const ref *pdref)
  217. {    dict *pdict = pdref->value.pdict;
  218.     uint space = ialloc_space(idmemory);
  219.     int code;
  220.  
  221.     ialloc_set_space(idmemory, r_space(pdref));
  222.     code = ialloc_ref_array(&pdict->keys, a_all, asize, "dict create unpacked keys");
  223.     if ( code >= 0 )
  224.       { ref *kp = pdict->keys.value.refs;
  225.         ref_mark_new(&pdict->keys);
  226.         refset_null(kp, asize);
  227.         r_set_attrs(kp, a_executable);    /* wraparound entry */
  228.       }
  229.     ialloc_set_space(idmemory, space);
  230.     return code;
  231. }
  232. /* Create the contents (keys and values) of a newly allocated dictionary. */
  233. /* Allocate in the current VM space, which is assumed to be the same as */
  234. /* the VM space where the dictionary is allocated. */
  235. private int
  236. dict_create_contents(uint size, const ref *pdref, bool pack)
  237. {    dict *pdict = pdref->value.pdict;
  238.     uint asize = dict_round_size((size == 0 ? 1 : size));
  239.     int code;
  240.     register uint i;
  241.  
  242.     if ( asize == 0 || asize > max_array_size - 1 )    /* too large */
  243.       return_error(e_limitcheck);
  244.     asize++;        /* allow room for wraparound entry */
  245.     code = ialloc_ref_array(&pdict->values, a_all, asize,
  246.                 "dict_create(values)");
  247.     if ( code < 0 )
  248.       return code;
  249.     ref_mark_new(&pdict->values);
  250.     refset_null(pdict->values.value.refs, asize);
  251.     if ( pack )
  252.        {    uint ksize = (asize + packed_per_ref - 1) / packed_per_ref;
  253.         ref arr;
  254.         ref_packed *pkp;
  255.         ref_packed *pzp;
  256.         code = ialloc_ref_array(&arr, a_all, ksize,
  257.                     "dict_create(packed keys)");
  258.         if ( code < 0 )
  259.           return code;
  260.         pkp = (ref_packed *)arr.value.refs;
  261.         make_tasv_new(&pdict->keys, t_shortarray,
  262.                   r_space(&arr) | a_all,
  263.                   asize, packed, pkp);
  264.         for ( pzp = pkp, i = 0; i < asize || i % packed_per_ref; pzp++, i++ )
  265.           *pzp = packed_key_empty;
  266.         *pkp = packed_key_deleted;    /* wraparound entry */
  267.        }
  268.     else                /* not packed */
  269.        {    int code = dict_create_unpacked_keys(asize, pdref);
  270.         if ( code < 0 ) return code;
  271.        }
  272.     make_int_new(&pdict->count, 0);
  273.     make_int_new(&pdict->maxlength, size);
  274.     return 0;
  275. }
  276.  
  277. /*
  278.  * Ensure that a dictionary uses the unpacked representation for keys.
  279.  * We can't just use dict_resize, because the values slots mustn't move.
  280.  */
  281. int
  282. dict_unpack(ref *pdref)
  283. {    dict *pdict = pdref->value.pdict;
  284.     if ( !dict_is_packed(pdict) )
  285.       return 0;            /* nothing to do */
  286.     {    uint count = nslots(pdict);
  287.         const ref_packed *okp = pdict->keys.value.packed;
  288.         ref old_keys;
  289.         int code;
  290.         ref *nkp;
  291.         old_keys = pdict->keys;
  292.         if ( ref_must_save(&old_keys) )
  293.           ref_do_save(pdref, &pdict->keys, "dict_unpack(keys)");
  294.         code = dict_create_unpacked_keys(count, pdref);
  295.         if ( code < 0 )
  296.           return code;
  297.         for ( nkp = pdict->keys.value.refs; count--; okp++, nkp++ )
  298.           if ( r_packed_is_name(okp) )
  299.             { packed_get(okp, nkp);
  300.               ref_mark_new(nkp);
  301.             }
  302.           else if ( *okp == packed_key_deleted )
  303.             r_set_attrs(nkp, a_executable);
  304.         if ( !ref_must_save(&old_keys) )
  305.           ifree_ref_array(&old_keys, "dict_unpack(old keys)");
  306.         dict_set_top();    /* just in case */
  307.     }
  308.     return 0;
  309. }
  310.  
  311. /*
  312.  * Define a macro for searching a packed dictionary.  Free variables:
  313.  *    ref_packed kpack - holds the packed key.
  314.  *    uint hash - holds the hash of the name.
  315.  *    dict *pdict - points to the dictionary.
  316.  *    uint size - holds npairs(pdict).
  317.  * Note that the macro is *not* enclosed in {}, so that we can access
  318.  * the values of kbot and kp after leaving the loop.
  319.  *
  320.  * We break the macro into two to avoid overflowing some preprocessors.
  321.  */
  322. /* packed_search_body also uses kp and kbot as free variables. */
  323. #define packed_search_value_pointer (pdict->values.value.refs + (kp - kbot))
  324. #define packed_search_body(found1,found2,del,miss)\
  325.     { if_debug2('D', "[D]probe 0x%lx: 0x%x\n", (ulong)kp, *kp);\
  326.       if ( *kp == kpack )\
  327.        { found1;\
  328.      found2;\
  329.        }\
  330.       else if ( !r_packed_is_name(kp) )\
  331.        { /* Empty, deleted, or wraparound. Figure out which. */\
  332.      if ( *kp == packed_key_empty ) miss;\
  333.      if ( kp == kbot ) break;    /* wrap */\
  334.      else { del; }\
  335.        }\
  336.     }
  337. #define packed_search_1(found1,found2,del,miss)\
  338.    const ref_packed *kbot = pdict->keys.value.packed;\
  339.    register const ref_packed *kp;\
  340.    for ( kp = kbot + dict_hash_mod(hash, size) + 1; ; kp-- )\
  341.      packed_search_body(found1,found2,del,miss)
  342. #define packed_search_2(found1,found2,del,miss)\
  343.    for ( kp += size; ; kp-- )\
  344.      packed_search_body(found1,found2,del,miss)
  345.  
  346. /*
  347.  * Look up a key in a dictionary.  Store a pointer to the value slot
  348.  * where found, or to the (value) slot for inserting.
  349.  * Return 1 if found, 0 if not and there is room for a new entry,
  350.  * or e_dictfull if the dictionary is full and the key is missing.
  351.  * The caller is responsible for ensuring key is not a null.
  352.  */
  353. int
  354. dict_find(const ref *pdref, const ref *pkey,
  355.   ref **ppvalue    /* result is stored here */)
  356. {    dict *pdict = pdref->value.pdict;
  357.     uint size = npairs(pdict);
  358.     register int etype;
  359.     uint nidx;
  360.     ref_packed kpack;
  361.     uint hash;
  362.     int ktype;
  363.     /* Compute hash.  The only types we bother with are strings, */
  364.     /* names, and (unlikely, but worth checking for) integers. */
  365.     switch ( r_type(pkey) )
  366.     {
  367.     case t_name:
  368.         nidx = name_index(pkey);
  369. nh:        hash = dict_name_index_hash(nidx);
  370.         kpack = packed_name_key(nidx);
  371.         ktype = t_name;
  372.         break;
  373.     case t_string:            /* convert to a name first */
  374.     {    ref nref;
  375.         int code;
  376.         if ( !r_has_attr(pkey, a_read) )
  377.           return_error(e_invalidaccess);
  378.         code = name_ref(pkey->value.bytes, r_size(pkey), &nref, 1);
  379.         if ( code < 0 )
  380.           return code;
  381.         nidx = name_index(&nref);
  382.     }    goto nh;
  383.     case t_integer:
  384.         hash = (uint)pkey->value.intval * 30503;
  385.         kpack = packed_key_impossible;
  386.         ktype = -1;
  387.         nidx = 0;        /* only to pacify gcc */
  388.         break;
  389.     case t_null:            /* not allowed as a key */
  390.         return_error(e_typecheck);
  391.     default:
  392.         hash = r_btype(pkey) * 99;    /* yech */
  393.         kpack = packed_key_impossible;
  394.         ktype = -1;
  395.         nidx = 0;        /* only to pacify gcc */
  396.     }
  397.     /* Search the dictionary */
  398.     if ( dict_is_packed(pdict) )
  399.     {    const ref_packed *pslot = 0;
  400.         packed_search_1(*ppvalue = packed_search_value_pointer,
  401.                 return 1,
  402.                 if ( pslot == 0 ) pslot = kp, goto miss);
  403.         packed_search_2(*ppvalue = packed_search_value_pointer,
  404.                 return 1,
  405.                 if ( pslot == 0 ) pslot = kp, goto miss);
  406.         /*
  407.          * Double wraparound, dict is full.
  408.          * Note that even if there was an empty slot (pslot != 0),
  409.          * we must return dictfull if length = maxlength.
  410.          */
  411.         if ( pslot == 0 || d_length(pdict) == d_maxlength(pdict) )
  412.           return(e_dictfull);
  413.         *ppvalue = pdict->values.value.refs + (pslot - kbot);
  414.         return 0;
  415. miss:        /* Key is missing, not double wrap.  See above re dictfull. */
  416.         if ( d_length(pdict) == d_maxlength(pdict) )
  417.           return(e_dictfull);
  418.         if ( pslot == 0 )
  419.           pslot = kp;
  420.         *ppvalue = pdict->values.value.refs + (pslot - kbot);
  421.         return 0;
  422.     }
  423.     else
  424.     {    ref *kbot = pdict->keys.value.refs;
  425.         register ref *kp;
  426.         ref *pslot = 0;
  427.         int wrap = 0;
  428.         for ( kp = kbot + dict_hash_mod(hash, size) + 2; ; )
  429.         {    --kp;
  430.             if ( (etype = r_type(kp)) == ktype )
  431.             {    /* Fast comparison if both keys are names */
  432.                 if ( name_index(kp) == nidx )
  433.                 {    *ppvalue = pdict->values.value.refs + (kp - kbot);
  434.                     return 1;
  435.                 }
  436.             }
  437.             else if ( etype == t_null )
  438.             {    /* Empty, deleted, or wraparound. */
  439.                 /* Figure out which. */
  440.                 if ( kp == kbot )    /* wrap */
  441.                 {    if ( wrap++ )    /* wrapped twice */
  442.                     {    if ( pslot == 0 )
  443.                           return(e_dictfull);
  444.                         break;
  445.                     }
  446.                     kp += size + 1;
  447.                    }
  448.                 else if ( r_has_attr(kp, a_executable) )
  449.                 {    /* Deleted entry, save the slot. */
  450.                     if ( pslot == 0 )
  451.                         pslot = kp;
  452.                 }
  453.                 else    /* key not found */
  454.                     break;
  455.             }
  456.             else
  457.             {    if ( obj_eq(kp, pkey) )
  458.                 {    *ppvalue = pdict->values.value.refs + (kp - kbot);
  459.                     return 1;
  460.                 }
  461.             }
  462.         }
  463.         if ( d_length(pdict) == d_maxlength(pdict) )
  464.           return(e_dictfull);
  465.         *ppvalue = pdict->values.value.refs +
  466.               ((pslot != 0 ? pslot : kp) - kbot);
  467.         return 0;
  468.     }
  469. }
  470.  
  471. /*
  472.  * Look up a (constant) C string in a dictionary.
  473.  * Return 1 if found, <= 0 if not.
  474.  */
  475. int
  476. dict_find_string(const ref *pdref, const char _ds *kstr, ref **ppvalue)
  477. {    int code;
  478.     ref kname;
  479.     if ( (code = name_ref((const byte *)kstr, strlen(kstr), &kname, -1)) < 0 )
  480.       return code;
  481.     return dict_find(pdref, &kname, ppvalue);
  482. }
  483.  
  484. /* Check whether a dictionary is one of the permanent ones on the d-stack. */
  485. bool
  486. dict_is_permanent_on_dstack(const ref *pdref)
  487. {    dict *pdict = pdref->value.pdict;
  488.     int i;
  489.     if ( d_stack.extension_size == 0 )
  490.       {    /* Only one block of d-stack. */
  491.         for ( i = 0; i < min_dstack_size; ++i )
  492.           if ( dsbot[i].value.pdict == pdict )
  493.             return true;
  494.       }
  495.     else
  496.       {    /* More than one block of d-stack. */
  497.         uint count = ref_stack_count(&d_stack);
  498.         for ( i = count - min_dstack_size; i < count; ++i )
  499.           if ( ref_stack_index(&d_stack, i)->value.pdict == pdict )
  500.             return true;
  501.       }
  502.     return false;
  503. }
  504.  
  505. /*
  506.  * Look up a name on the dictionary stack.
  507.  * Return the pointer to the value if found, 0 if not.
  508.  */
  509. ref *
  510. dict_find_name_by_index(uint nidx)
  511. {    ds_ptr pdref = dsp;
  512. /* Since we know the hash function is the identity function, */
  513. /* there's no point in allocating a separate variable for it. */
  514. #define hash dict_name_index_hash(nidx)
  515.     ref_packed kpack = packed_name_key(nidx);
  516.     do
  517.        {    dict *pdict = pdref->value.pdict;
  518.         uint size = npairs(pdict);
  519. #ifdef DEBUG
  520.         if ( gs_debug_c('D') )
  521.         {    ref dnref;
  522.             name_index_ref(nidx, &dnref);
  523.             dputs("[D]lookup ");
  524.             debug_print_name(&dnref);
  525.             dprintf3(" in 0x%lx(%u/%u)\n",
  526.                  (ulong)pdict, dict_length(pdref),
  527.                  dict_maxlength(pdref));
  528.         }
  529. #endif
  530.         if ( dict_is_packed(pdict) )
  531.            {    packed_search_1(DO_NOTHING,
  532.                     return packed_search_value_pointer,
  533.                     DO_NOTHING, goto miss);
  534.             packed_search_2(DO_NOTHING,
  535.                     return packed_search_value_pointer,
  536.                     DO_NOTHING, break);
  537.  miss:            ;
  538.            }
  539.         else
  540.            {    ref *kbot = pdict->keys.value.refs;
  541.             register ref *kp;
  542.             int wrap = 0;
  543.             /* Search the dictionary */
  544.             for ( kp = kbot + dict_hash_mod(hash, size) + 2; ; )
  545.                {    --kp;
  546.                 if ( r_has_type(kp, t_name) )
  547.                    {    if ( name_index(kp) == nidx )
  548.                       return pdict->values.value.refs +
  549.                         (kp - kbot);
  550.                    }
  551.                 else if ( r_has_type(kp, t_null) )
  552.                    {    /* Empty, deleted, or wraparound. */
  553.                     /* Figure out which. */
  554.                     if ( !r_has_attr(kp, a_executable) )
  555.                       break;
  556.                     if ( kp == kbot )    /* wrap */
  557.                        {    if ( wrap++ )
  558.                           break;    /* 2 wraps */
  559.                         kp += size + 1;
  560.                        }
  561.                    }
  562.                }
  563.            }
  564.        }
  565.     while ( pdref-- > dsbot );
  566.     /* The name isn't in the top dictionary block. */
  567.     /* If there are other blocks, search them now (more slowly). */
  568.     if ( !d_stack.extension_size )        /* no more blocks */
  569.       return (ref *)0;
  570.     {    /* We could use the STACK_LOOP macros, but for now, */
  571.         /* we'll do things the simplest way. */
  572.         ref key;
  573.         uint i = dsp + 1 - dsbot;
  574.         uint size = ref_stack_count(&d_stack);
  575.         ref *pvalue;
  576.         name_index_ref(nidx, &key);
  577.         for ( ; i < size; i++ )
  578.           {    if ( dict_find(ref_stack_index(&d_stack, i),
  579.                        &key, &pvalue) > 0
  580.                )
  581.               return pvalue;
  582.           }
  583.     }
  584.     return (ref *)0;
  585. #undef hash
  586. }
  587.  
  588. /*
  589.  * Enter a key-value pair in a dictionary.
  590.  * See idict.h for the possible return values.
  591.  */
  592. int
  593. dict_put(ref *pdref /* t_dictionary */, const ref *pkey, const ref *pvalue)
  594. {    int rcode = 0;
  595.     int code;
  596.     ref *pvslot;
  597.     /* Check the value. */
  598.     store_check_dest(pdref, pvalue);
  599. top:    if ( (code = dict_find(pdref, pkey, &pvslot)) <= 0 )    /* not found */
  600.        {    /* Check for overflow */
  601.         dict *pdict = pdref->value.pdict;
  602.         ref kname;
  603.         uint index;
  604.         switch ( code )
  605.           {
  606.           case 0:
  607.             break;
  608.           case e_dictfull:
  609.             if ( !dict_auto_expand )
  610.               return_error(e_dictfull);
  611.             code = dict_grow(pdref);
  612.             if ( code < 0 )
  613.               return code;
  614.             goto top;    /* keep things simple */
  615.           default:    /* e_typecheck */
  616.             return code;
  617.           }
  618.         index = pvslot - pdict->values.value.refs;
  619.         /* If the key is a string, convert it to a name. */
  620.         if ( r_has_type(pkey, t_string) )
  621.           {    int code;
  622.             if ( !r_has_attr(pkey, a_read) )
  623.               return_error(e_invalidaccess);
  624.             code = name_from_string(pkey, &kname);
  625.             if ( code < 0 )
  626.               return code;
  627.             pkey = &kname;
  628.            }
  629.         if ( dict_is_packed(pdict) )
  630.            {    ref_packed *kp;
  631.             if ( !r_has_type(pkey, t_name) ||
  632.                  name_index(pkey) > packed_name_max_index
  633.                )
  634.                {    /* Change to unpacked representation. */
  635.                 int code = dict_unpack(pdref);
  636.                 if ( code < 0 )
  637.                   return code;
  638.                 goto top;
  639.                }
  640.             kp = (ref_packed *)(pdict->keys.value.packed + index);
  641.             if ( ref_must_save(&pdict->keys) )
  642.                {    /* See initial comment for why it is safe */
  643.                 /* not to save the change if the keys */
  644.                 /* array itself is new. */
  645.                 ref_do_save(&pdict->keys, kp, "dict_put(key)");
  646.                }
  647.             *kp = pt_tag(pt_literal_name) + name_index(pkey);
  648.            }
  649.         else
  650.            {    ref *kp = pdict->keys.value.refs + index;
  651.             if_debug2('d', "[d]0x%lx: fill key at 0x%lx\n",
  652.                   (ulong)pdict, (ulong)kp);
  653.             store_check_dest(pdref, pkey);
  654.             ref_assign_old(&pdict->keys, kp, pkey,
  655.                        "dict_put(key)");    /* set key of pair */
  656.            }
  657.         ref_save(pdref, &pdict->count, "dict_put(count)");
  658.         pdict->count.value.intval++;
  659.         /* If the key is a name, update its 1-element cache. */
  660.         if ( r_has_type(pkey, t_name) )
  661.            {    name *pname = pkey->value.pname;
  662.             if ( pname->pvalue == pv_no_defn &&
  663.                 (pdict == systemdict->value.pdict ||
  664.                  dict_is_permanent_on_dstack(pdref)) &&
  665.                 /* Only set the cache if we aren't inside */
  666.                 /* a save.  This way, we never have to */
  667.                 /* undo setting the cache. */
  668.                 alloc_save_level(idmemory) == 0
  669.                )
  670.                {    /* Set the cache. */
  671.                 if_debug0('d', "[d]set cache\n");
  672.                 pname->pvalue = pvslot;
  673.                }
  674.             else
  675.               {    /* The cache can't be used. */
  676.                 if_debug0('d', "[d]no cache\n");
  677.                 pname->pvalue = pv_other;
  678.               }
  679.            }
  680.         rcode = 1;
  681.        }
  682.     if_debug8('d', "[d]0x%lx: put key 0x%lx 0x%lx\n  value at 0x%lx: old 0x%lx 0x%lx, new 0x%lx 0x%lx\n",
  683.           (ulong)pdref->value.pdict,
  684.           ((const ulong *)pkey)[0], ((const ulong *)pkey)[1],
  685.           (ulong)pvslot,
  686.           ((const ulong *)pvslot)[0], ((const ulong *)pvslot)[1],
  687.           ((const ulong *)pvalue)[0], ((const ulong *)pvalue)[1]);
  688.     ref_assign_old(&pdref->value.pdict->values, pvslot, pvalue,
  689.                "dict_put(value)");
  690.     return rcode;
  691. }
  692.  
  693. /*
  694.  * Enter a key-value pair where the key is a (constant) C string.
  695.  */
  696. int
  697. dict_put_string(ref *pdref, const char *kstr, const ref *pvalue)
  698. {    int code;
  699.     ref kname;
  700.     if ( (code = name_ref((const byte *)kstr, strlen(kstr), &kname, 0)) < 0 )
  701.       return code;
  702.     return dict_put(pdref, &kname, pvalue);
  703. }
  704.  
  705. /* Remove an element from a dictionary. */
  706. int
  707. dict_undef(ref *pdref, const ref *pkey)
  708. {    ref *pvslot;
  709.     dict *pdict;
  710.     uint index;
  711.     if ( dict_find(pdref, pkey, &pvslot) <= 0 )
  712.       return(e_undefined);
  713.     /* Remove the entry from the dictionary. */
  714.     pdict = pdref->value.pdict;
  715.     index = pvslot - pdict->values.value.refs;
  716.     if ( dict_is_packed(pdict) )
  717.        {    ref_packed *pkp =
  718.            (ref_packed *)(pdict->keys.value.packed + index);
  719.         /* See the initial comment for why it is safe not to save */
  720.         /* the change if the keys array itself is new. */
  721.         if ( ref_must_save(&pdict->keys) )
  722.           ref_do_save(&pdict->keys, pkp, "dict_undef(key)");
  723.         /* Accumulating deleted entries slows down lookup. */
  724.         /* Detect the easy case where we can use an empty entry */
  725.         /* rather than a deleted one, namely, when the next entry */
  726.         /* in the probe order is empty. */
  727.         if ( pkp[-1] == packed_key_empty )
  728.           *pkp = packed_key_empty;
  729.         else
  730.           *pkp = packed_key_deleted;
  731.        }
  732.     else                /* not packed */
  733.        {    ref *kp = pdict->keys.value.refs + index;
  734.         make_null_old(&pdict->keys, kp, "dict_undef(key)");
  735.         /* Accumulating deleted entries slows down lookup. */
  736.         /* Detect the easy case where we can use an empty entry */
  737.         /* rather than a deleted one, namely, when the next entry */
  738.         /* in the probe order is empty. */
  739.         if ( !r_has_type(kp - 1, t_null) ||    /* full entry */
  740.              r_has_attr(kp - 1, a_executable)    /* deleted or wraparound */
  741.             )
  742.           r_set_attrs(kp, a_executable);    /* mark as deleted */
  743.        }
  744.     ref_save(pdref, &pdict->count, "dict_undef(count)");
  745.     pdict->count.value.intval--;
  746.     /* If the key is a name, update its 1-element cache. */
  747.     if ( r_has_type(pkey, t_name) )
  748.       {    name *pname = pkey->value.pname;
  749.         if ( pv_valid(pname->pvalue) )
  750.           {
  751. #ifdef DEBUG
  752.             /* Check the the cache is correct. */
  753.             if ( !dict_is_permanent_on_dstack(pdref) )
  754.               lprintf1("dict_undef: cached name value pointer 0x%lx is incorrect!\n",
  755.                    (ulong)pname->pvalue);
  756. #endif
  757.             /* Clear the cache */
  758.             pname->pvalue = pv_no_defn;
  759.           }
  760.       }
  761.     make_null_old(&pdict->values, pvslot, "dict_undef(value)");
  762.     return 0;
  763. }
  764.  
  765. /* Return the number of elements in a dictionary. */
  766. uint
  767. dict_length(const ref *pdref /* t_dictionary */)
  768. {    return d_length(pdref->value.pdict);
  769. }
  770.  
  771. /* Return the capacity of a dictionary. */
  772. uint
  773. dict_maxlength(const ref *pdref    /* t_dictionary */)
  774. {    return d_maxlength(pdref->value.pdict);
  775. }
  776.  
  777. /* Return the maximum index of a slot within a dictionary. */
  778. uint
  779. dict_max_index(const ref *pdref    /* t_dictionary */)
  780. {    return npairs(pdref->value.pdict) - 1;
  781. }
  782.  
  783. /* Copy one dictionary into another. */
  784. /* If new_only is true, only copy entries whose keys */
  785. /* aren't already present in the destination. */
  786. int
  787. dict_copy_entries(const ref *pdrfrom /* t_dictionary */,
  788.   ref *pdrto /* t_dictionary */, bool new_only)
  789. {    int space = r_space(pdrto);
  790.     int index;
  791.     ref elt[2];
  792.     ref *pvslot;
  793.     int code;
  794.     if ( space != avm_max )
  795.       {    /* Do the store check before starting the copy. */
  796.         index = dict_first(pdrfrom);
  797.         while ( (index = dict_next(pdrfrom, index, elt)) >= 0 )
  798.           if ( !new_only || dict_find(pdrto, &elt[0], &pvslot) <= 0 )
  799.           {    store_check_space(space, &elt[0]);
  800.             store_check_space(space, &elt[1]);
  801.           }
  802.       }
  803.     /* Now copy the contents. */
  804.     index = dict_first(pdrfrom);
  805.     while ( (index = dict_next(pdrfrom, index, elt)) >= 0 )
  806.       {    if ( new_only && dict_find(pdrto, &elt[0], &pvslot) > 0 )
  807.           continue;
  808.         if ( (code = dict_put(pdrto, &elt[0], &elt[1])) < 0 )
  809.           return code;
  810.       }
  811.     return 0;
  812. }
  813.  
  814. /* Set the cached values computed from the top entry on the dstack. */
  815. /* See dstack.h for details. */
  816. private const ref_packed no_packed_keys[2] =
  817.     { packed_key_deleted, packed_key_empty };
  818. void
  819. dict_set_top(void)
  820. {    dict *pdict = dsp->value.pdict;
  821.     if_debug3('d', "[d]dsp = 0x%lx -> 0x%lx, key array type = %d\n",
  822.           (ulong)dsp, (ulong)pdict, r_type(&pdict->keys));
  823.     if ( dict_is_packed(pdict) &&
  824.          r_has_attr(dict_access_ref(dsp), a_read)
  825.        )
  826.     {    dtop_keys = pdict->keys.value.packed;
  827.         dtop_npairs = npairs(pdict);
  828.         dtop_values = pdict->values.value.refs;
  829.     }
  830.     else
  831.     {    dtop_keys = no_packed_keys;
  832.         dtop_npairs = 1;
  833.     }
  834.     if ( !r_has_attr(dict_access_ref(dsp), a_write) )
  835.         dsspace = -1;
  836.     else
  837.         dsspace = r_space(dsp);
  838. }
  839.  
  840. /* Resize a dictionary. */
  841. int
  842. dict_resize(ref *pdref, uint new_size)
  843. {    dict *pdict = pdref->value.pdict;
  844.     dict dnew;
  845.     ref drto;
  846.     int code;
  847.     uint space;
  848.     if ( new_size < d_length(pdict) )
  849.     {    if ( !dict_auto_expand )
  850.           return_error(e_dictfull);
  851.         new_size = d_length(pdict);
  852.     }
  853.     space = ialloc_space(idmemory);
  854.     ialloc_set_space(idmemory, r_space(pdref));
  855.     make_tav_new(&drto, t_dictionary, r_space(pdref) | a_all,
  856.              pdict, &dnew);
  857.     if ( (code = dict_create_contents(new_size, &drto, dict_is_packed(pdict))) < 0 )
  858.     {    ialloc_set_space(idmemory, space);
  859.         return code;
  860.     }
  861.     /* We must suppress the store check, in case we are expanding */
  862.     /* systemdict or another global dictionary that is allowed */
  863.     /* to reference local objects. */
  864.     r_set_space(&drto, avm_local);
  865.     dict_copy(pdref, &drto);    /* can't fail */
  866.     /* Save or free the old dictionary. */
  867.     if ( ref_must_save(&pdict->values) )
  868.       ref_do_save(pdref, &pdict->values, "dict_resize(values)");
  869.     else
  870.       ifree_ref_array(&pdict->values, "dict_resize(old values)");
  871.     if ( ref_must_save(&pdict->keys) )
  872.       ref_do_save(pdref, &pdict->keys, "dict_resize(keys)");
  873.     else
  874.       ifree_ref_array(&pdict->keys, "dict_resize(old keys)");
  875.     ref_assign(&pdict->keys, &dnew.keys);
  876.     ref_assign(&pdict->values, &dnew.values);
  877.     ref_save(pdref, &pdict->maxlength, "dict_resize(maxlength)");
  878.     d_set_maxlength(pdict, new_size);
  879.     ialloc_set_space(idmemory, space);
  880.     dict_set_top();        /* just in case this is the top dict */
  881.     return 0;
  882. }
  883.  
  884. /* Grow a dictionary for dict_put. */
  885. int
  886. dict_grow(ref *pdref)
  887. {    dict *pdict = pdref->value.pdict;
  888.     /* We might have maxlength < npairs, if */
  889.     /* dict_round_size increased the size. */
  890.     ulong new_size = (ulong)d_maxlength(pdict) * 3 / 2 + 2;
  891.  
  892. #if arch_sizeof_int < arch_sizeof_long
  893.     if ( new_size > max_uint )
  894.       new_size = max_uint;
  895. #endif
  896.     if ( new_size > npairs(pdict) )
  897.     {    int code = dict_resize(pdref, (uint)new_size);
  898.         if ( code >= 0 )
  899.           return code;
  900.         /* new_size was too big. */
  901.         if ( npairs(pdict) < dict_max_size )
  902.           { code = dict_resize(pdref, dict_max_size);
  903.             if ( code >= 0 )
  904.               return code;
  905.           }
  906.         if ( npairs(pdict) == d_maxlength(pdict) )
  907.           { /* Can't do it. */
  908.             return code;
  909.           }
  910.         /* We can't grow to new_size, but we can grow to npairs. */
  911.         new_size = npairs(pdict);
  912.     }
  913.     /* maxlength < npairs, we can grow in place */
  914.     ref_save(pdref, &pdict->maxlength, "dict_put(maxlength)");
  915.     d_set_maxlength(pdict, new_size);
  916.     return 0;
  917. }
  918.  
  919. /* Prepare to enumerate a dictionary. */
  920. int
  921. dict_first(const ref *pdref)
  922. {    return (int)nslots(pdref->value.pdict);
  923. }
  924.  
  925. /* Enumerate the next element of a dictionary. */
  926. int
  927. dict_next(const ref *pdref, int index, ref *eltp /* ref eltp[2] */)
  928. {    dict *pdict = pdref->value.pdict;
  929.     ref *vp = pdict->values.value.refs + index;
  930.     while ( vp--, --index >= 0 )
  931.        {    array_get(&pdict->keys, (long)index, eltp);
  932.         /* Make sure this is a valid entry. */
  933.         if ( r_has_type(eltp, t_name) ||
  934.              (!dict_is_packed(pdict) && !r_has_type(eltp, t_null))
  935.            )
  936.            {    eltp[1] = *vp;
  937.             if_debug6('d', "[d]0x%lx: index %d: %lx %lx, %lx %lx\n",
  938.                 (ulong)pdict, index,
  939.                 ((ulong *)eltp)[0], ((ulong *)eltp)[1],
  940.                 ((ulong *)vp)[0], ((ulong *)vp)[1]);
  941.             return index;
  942.            }
  943.        }
  944.     return -1;            /* no more elements */
  945. }
  946.  
  947. /* Return the index of a value within a dictionary. */
  948. int
  949. dict_value_index(const ref *pdref, const ref *pvalue)
  950. {    return (int)(pvalue - pdref->value.pdict->values.value.refs - 1);
  951. }
  952.  
  953. /* Return the entry at a given index within a dictionary. */
  954. /* If the index designates an unoccupied entry, return e_undefined. */
  955. int
  956. dict_index_entry(const ref *pdref, int index, ref *eltp /* ref eltp[2] */)
  957. {    const dict *pdict = pdref->value.pdict;
  958.     array_get(&pdict->keys, (long)(index + 1), eltp);
  959.     if ( r_has_type(eltp, t_name) ||
  960.          (!dict_is_packed(pdict) && !r_has_type(eltp, t_null))
  961.        )
  962.       {    eltp[1] = pdict->values.value.refs[index + 1];
  963.         return 0;
  964.       }
  965.     return e_undefined;
  966. }
  967.  
  968. /* After a garbage collection, scan the permanent dictionaries and */
  969. /* update the cached value pointers in names. */
  970. void
  971. dstack_gc_cleanup(void)
  972. {    uint count = ref_stack_count(&d_stack);
  973.     uint dsi;
  974.     for ( dsi = min_dstack_size; dsi > 0; --dsi )
  975.       {    const dict *pdict =
  976.           ref_stack_index(&d_stack, count - dsi)->value.pdict;
  977.         uint size = nslots(pdict);
  978.         ref *pvalue = pdict->values.value.refs;
  979.         uint i;
  980.         for ( i = 0; i < size; ++i, ++pvalue )
  981.           {    ref key;
  982.             ref *old_pvalue;
  983.             array_get(&pdict->keys, (long)i, &key);
  984.             if ( r_has_type(&key, t_name) &&
  985.                  pv_valid(old_pvalue = key.value.pname->pvalue)
  986.                )
  987.               {    /*
  988.                  * The name only has a single definition,
  989.                  * so it must be this one.  Check to see if
  990.                  * no relocation is actually needed; if so,
  991.                  * we can skip the entire dictionary.
  992.                  */
  993.                 if ( old_pvalue == pvalue )
  994.                   {    if_debug1('d', "[d]skipping dstack entry %d\n",
  995.                           dsi - 1);
  996.                     break;
  997.                   }
  998.                 /* Update the value pointer. */
  999.                 key.value.pname->pvalue = pvalue;
  1000.               }
  1001.           }
  1002.       }
  1003. }
  1004.